\junk{
Nature of contagion.

Network model.

Game-theoretic or not.

Protection mechanisms

Our work: Protection against contagion in decentralized dynamic
networks

Nature of contagion: Harmful (diseases, computer viruses)

Network model: arbitrary as well real-world complex network models

Game-theoretic models:
}
%------------------------------
\section{Related work}
\label{sec:related}
In this section, we review related work that is most relevant to our
project.  We have classified previous research according to the
primary motivating domain of the work (epidemiology, social networks
and economics, or network security).  We also give a brief overview of
some of mathematical and computational techniques and models that have
been developed in previous work and would play an important role in
our project.

\smallskip
\BfPara{Epidemiology} The study of the spread of diseases and ways to control them has been a major scientific endeavor for centuries.  One of 
the earliest documented scientific studies of vaccination policy was
due to Bernoulli, who analyzed smallpox morbidity and mortality data
to demonstrate the effectiveness of
vaccination~\cite{blower:bernoulli}.  He presented a mathematical
model for calculating the costs and benefits of smallpox vaccination,
and presented a convincing mathematical analysis for universal
vaccination.  Modern epidemiological analysis is largely based on an
elegant class of models called the SIR
(susceptible-infected-recovered).  First formulated by Reed and Frost
on the 1920s, it has been developed over several decades, starting
from the work of Kermack and McKendrick~\cite{kermack+m:SIR} leading
to the compartmental modeling approach due to Anderson and
May~\cite{anderson+m:book} aimed at predicting transmission for a wide
range of diseases.  In the SIR model, the population is divided into
three states: susceptible (S), infected (I), and recovered (R).  A
{\em susceptible}\/ individual becomes {\em infected}\/ at a certain
rate depending on the contact with other infected individuals.  Once
infected, an individual may either recover and receive lifelong
immunity or die; in either case, it moves to the {\em recovered}\/
state.  Another well-studied model is the SIS
(susceptible-infected-susceptible) model which differs from the SIR
model in the aspect that when an individual recovers from an
infection, they move back to the susceptible state~\cite{weiss+d:SIS}.

The SIR model and its variants have been highly influential in the
study of
epidemics~\cite{yang+h1n109,manski+partial10,medlock+optvacc09,kaplan+smallpox02,grassly+model08,blower+imperfect93}.
These models, however, do not attempt to capture the rich structure of
the contact network along which interactions occur, an aspect that is
integral to our project.  In the emerging area of contact network
epidemiology, an underlying contact graph captures the patterns of
interactions leading to the transmission of a
disease~\cite{lloyd+m:epidemiology,meyers06,meyers+sars05,newman:spread02}.
Many studies have predicted the spread of diseases through networks
using mathematical analysis or simulations; e.g., estimating the size
of an epidemic, or determining the basic reproductive rate
(see~\cite{meyers06} for several pointers).

Over the past decade, a number of researchers have analyzed the
effectiveness of control strategies in a game-theoretic
setting~\cite{bauch+game03,bauch+game04,bauch:dynamic05,cojocaru08}.
Such studies enable the comparison of utilitarian optimum intervention
policies (e.g., vaccination or social distancing) or those proposed by
health agencies (e.g., CDC) with Nash equilibria strategies driven by
self-interest~\cite{AspnesCY2006,galvani+rc:influenza07}.

A major focus of our research project is on how intervention
strategies may in turn cause risky behavior and affect network
dynamics, which significantly affect the steady state equilibrium and
resulting social outcomes.  The counterintuitive impact of vaccination
owing to risky behavior was first discovered by Blower and
McLean~\cite{blower+risk94,blower:chapter} in the case of HIV.
Subsequently, several independent studies have confirmed this
phenomenon and have offered potential
explanations~\cite{smith+b:hiv04,bezemer08,wilson+cwb,velasco}.  No
formal models have been proposed, however, for studying the interplay
between interventions, network dynamics, and individual behavior in
the spread and control of contagion.

\smallskip
\BfPara{Social networks and economics}
The spread of contagion, influence, or behavior, in social networks
has been extensively studied.  This has spawned the research area of
{\em network games}, starting from the seminal work of Jackson and
Wolinsky~\cite{jackson+wolinsky:strategic}, and Bala and
Goyal~\cite{BalaGoyal} on how networks are formed when individuals
choose to add or sever links so as to maximize their influence.  A
variety of game-theoretic models have been developed to study diverse
applications including the very formation of
networks~\cite{jackson+wolinsky:strategic,BalaGoyal,johari-contractbased,fabrikant03network},
provision of public goods~\cite{bramoulle+k:networks}, and research
collaboration among firms~\cite{goyal+m:RandD}.
(See~\cite{jackson:book,goyal:book,galeotti+gjvy:network} for
excellent overviews of this research area.)  Most relevant to this
project is prior work on the diffusion of social and economic behavior
in networks, e.g., purchase of a product or adoption of a
technology~\cite{galeotti:consumer}, decision to undertake criminal
activity~\cite{ballester+cz:network}.  While much of prior research
has assumed that perfect information is available to all players, more
recent work has developed models for incomplete
information~\cite{galeotti+gjvy:network,jackson+y:diffusion}.  
There are several
fundamental differences between our proposed project and this line of
previous research.  First, the focus of our work is on the {\em impact
of intervention strategies on the spread of contagion}, rather than
analyzing how contagions spread.  Second, we take into account {\em
changes in the network} in the course of the diffusion process.
Third, we consider a much {\em richer strategy space}\/ which takes
into account temporal issues (when an intervention is adopted) and the
strength of the interventions; in contrast, previous work assumes
binary strategy spaces.

There is a huge body of work on {\em gossiping}, applied to both the
spread of ideas in a social network as well as routing or broadcast of
data in a communication
network~\cite{karp+ssv:rumor,feige+pru:broadcast,pittel:rumor,boyd+gps:gossip}.
Several analyses have been given for gossip-based routing
protocols~\cite{braginsky+e:rumor,elsasser+s:broadcast,kempe+k:gossip}.
Gossiping has also proved effective in aggregate computations in
distributed networks~\cite{kempe+dg:gossip,deb+mc:gossip}.  Recent
work has considered gossiping in dynamic adversarial
networks~\cite{avin+kl:dynamic,kuhn+lo:dynamic}.  Combinatorial
optimization aspects of influence spread are explored
in \cite{KempeKT03,KempeKT05} where the goal is to pick an initial set
in a stochastic model with maximal expected influence. This model is
extended further in \cite{BharathiKS07} to a competitive setting
within the stochastic framework where different players compete
(sequentially) to maximize their expected influence.

\junk{
for the nodes; instead they consider undirected links, and the nodes
optimize a cost which is the sum of the number of edges, scaled by a
parameter $\alpha > 0$, and the sum of distances to the rest of the
nodes.  They present several results on the price of anarchy, which is
the ratio of the cost of the worst-case Nash equilibrium to the social
optimum cost~\cite{koutsoupias99worst}.  Further results in this direction are 
obtained in~\cite{albers+eemr:nash}. \cite{Even-DarK06} is similar to \cite{fabrikant03network}
in that they impose a cost for the purchase of a link rather than a fixed budget, however
they consider a stochastic model and associated small-world effects.  
In~\cite{moscibroda06topologies} a variant is studied, in which the 
nodes are embedded in a metric space and
the distance component of the cost is replaced by the stretch with
respect to the metric. They obtain tight bounds on the price of
anarchy and show that the problem of deciding the existence of pure
Nash equilibria is NP-hard. Network formation under the requirement 
for bilateral consent for building links is studied in~\cite{corbo05}. 
Our model follows directly in the tradition of 
\cite{chun04:characterizing,Laoutaris2007:SNS} where they present experimental 
studies of network formation games involving non-unit link lengths. 

Network formation games have also been studied in the context of
Internet inter-domain routing.  A coalitional game-theoretic problem
modeling of BGP is introduced in
\cite{papadimitriou01algorithms} and studied further in
\cite{markakis03core}.  Also related is the work on designing strategy-proof mechanisms for
BGP~\cite{feigenbaum02bgpbased} as well as the recent work on
strategic network formation through AS-level
contracts~\cite{Anshelevich06:FOCS}. \cite{johari-contractbased} consider a 
contracts-based model of network formation where links do not have predefined
costs but are subject to negotiation and nodes attempt to minimize incoming
traffic by obtaining compensation in return.
}

\smallskip
\BfPara{Computer viruses and networking}
Several researchers have analyzed network security problems and the
spread of viral epidemics in
networks~\cite{AspnesCY2006,berger+episcalefree05,ganesh05,grossklags,lelarge+b:security,wang03}.
Another direction of work is based on SIS models for the worm spread,
e.g., the $n$-intertwined model~\cite{orda:infocom09}. In this model,
nodes are in two states: susceptible or infected. Each infected node
spreads the infection to its neighbors with some probability.  Another
closely related class of models is that of Interdependent Security
games (IDS)~\cite{kearns:ids}.

Non-cooperative game theory has been used in analyzing a number of
problems in traffic and communication networks, e.g., routing
\cite{roughgarden}, topology control and network formation 
\cite{eidenbenz06,nahir:infocom09}
and security \cite{grossklags,orda:infocom09}. The basic questions of
interest have usually been about the existence and the structure of
Nash equilibria and the price of anarchy, which is the worst case cost
of a Nash equilibrium to the social
optimum~\cite{koutsoupias99worst}. See~\cite{nisan:book} for a good
introduction on the use of game theoretic techniques for networking
applications.

\smallskip
\BfPara{Models and techniques}
The SIR, SIS, and related models in epidemiology can be characterized
in terms of differential equations that capture the rate of change of
the susceptible, infected, and recovered individuals.  Contact network
epidemiology enhances these models with a contact graph.  Contact
graphs are also integral aspects of models in network security and
social networks.  A number of random graph models have been considered
for modeling contacts (e.g.,
~\cite{meyers+sars05,gardenes+biscalefree07,meloni+episcalefree09}).
The most basic random graph model due to Erd\"{o}s and
R\'{e}nyi~\cite{erdos1960} and Gilbert~\cite{gilbert59}, who defined
the $G(n,m)$ and $G(n,p)$ models; in the former, a graph is chosen
uniformly at random from all $n$-vertex $m$-edge graphs, while the
latter is an $n$-vertex graph in which each edge appears uniformly and
independently at random with probability $p$.  A number of alternative
random graph models have been suggested in an attempt to yield random
graphs with more general types of degree distribution. Molloy and
Reed's model is based on considering random graphs of fixed order with
a given arbitrary degree
distribution~\cite{molloy+arbitrarydegree95,molloy+arbitrarydegree98,newman+arbitrarydegree01}. Later
Chung and Lu proposed a model to generate random graphs with expected
degree distribution~\cite{chung+ccsize02,chung+distance03}.  Other
models motivated by specific real-world networks include Kleinberg's
small world random graph
\cite{kleinberg+nature00,kleinberg+smallworld00}, Barab\'{a}si-Albert
preferential attachment graph \cite{barabasi:science99}.  The
preferential attachment model is a mechanism for generating scale-free
graphs~\cite{barabasi:science99,bollobas+degreeseq01}, which have
been observed to capture important properties of several real world
networks, including the Internet AS-level graph
\cite{faloutsos+powerlaw99}, the Worldwide Web
\cite{barabasi+web99,kleinberg+webgraph99}, human sexual contact network
\cite{liljeros+sexnet01}, scientific collaborations network
\cite{barabasi+collaboration02}), and the preferential attachment
process generates random scale-free graphs. \junk{Scale-free graphs have
been shown to be robust under random errors but vulnerable under
targeting
attacks~\cite{albert+errorattack00,bollobas+errorattack04}. The
diameter of scale-free graph is $O(\log n/\log\log n)$
\cite{bollobas+diameter04}. For a survey of scale-free graph, refer to
\cite{albert+survey02}. \cite{bollobas+survey03} is also a good survey
containing rigorous results on scale-free graph.}

The spread of contagion in networks has been analyzed by a variety of
methods: model-based
simulations~\cite{albert+errorattack00,pastor+episcalefree,cornforth+rsbgm:flu};
percolation theory techniques using differential equations and
generating functions that yield asymptotic
analyses~\cite{soderberg+inhomo02,newman:spread02,wormald:differential};
rigorous probabilistic techniques that apply to finite random
graph
models~\cite{bollobas+inhomo,bollobas+errorattack04,berger+episcalefree05};
and game-theoretic analyses that study uniqueness, complexity, and
structure of
equilibria~\cite{chen+dk:vaccinate,nisan:book,jackson+y:diffusion,galeotti+gjvy:network};
.

\junk{
There has been a lot of research on disease transmission over contact
networks using SIS model. Let $\beta$ be virus transmission
probability, $\nu$ be recovery probability of an infected node. And
define an effective spreading rate to be $\lambda=\beta/\nu$. In some
graphs, like regular lattice, there is threshold $\lambda_c$ such that
if $\lambda > \lambda_c$ the virus will persist, which if $\lambda <
\lambda_c$ the virus will die out quickly. \cite{pastor+episcalefree}
(by simulation) and \cite{berger+episcalefree05} (rigorously) show
that for scale-free graphs the threshold vanishes, i.e. $\lambda_c =
0$. This implies that on such networks even weakly infectious viruses
can spread and prevail. Then how to eradicate disease in scale-free
graphs become crucial. \cite{dezso+virus02} studies virus spreading
with cures. It shows (in simulation) that we can restore the
threshold, $\lambda_c > 0$, with biased strategies, i.e. apply cures
to the hubs with higher probability than less connected
nodes. \cite{borgs+antidote10} studies the same problem as
\cite{dezso+virus02}, but rigorously. They show the same results
mathematically. In general graphs,
\cite{ganesh+topology05,wang+eigenvalue03} show that the epidemic time
has close relationship with the topological properties of the graph:
(1) a sufficient condition for a quick die out is that $\lambda$ not
exceed the spectral radius of the adjacency matrix of the underlying
topology graph; (2) a sufficient condition for slow die out is that
$\lambda$ is larger than the isoperimetric constant associated with
the graph. All the work above study the epidemic time under SIS
model. Little work has been done on the epidemic size under SIS
model. \cite{kessler+episize08} studies such problem using
differential equations, i.e. no contact graph is considered. It would
be interesting to study the epidemic size on contact graphs.
}


\junk{In of Aspnes et al. \cite{AspnesCY2006}, who model the
risk of infection for an insecure node $v$ as the probability that the
initial infection, which is assumed to originate at a node chosen
uniformly at random, starts in the same component as $v$ in the
subgraph induced by $v$ and the other insecure nodes.  They show the
surprising result that pure Nash equilibria always exist in such
games.  They also establish a high price of anarchy and give an
$O(\log^{1.5}{n})$ approximation algorithm for computing the social
optimum, where $n$ is the number of nodes in the network.  Their
approximation algorithm uses an $O(\sqrt{\log n})$-approximation for
the sparsest cut problem~\cite{arora+rv:cut}, which is based on a
semidefinite programming relaxation of the problem.  In this paper, we
are able to give a much simpler LP-based approximation algorithm using
the vertex multi-cut problem, which improves the approximation ratio
to $O(\log n)$ and also applies to a more general model.}

\junk{One difficulty with these models is the
information needed to compute the utility function since calculating
infection probabilities is \#P-complete in general. } 

\junk{ which is similar to our model for the special
case of $d = 1$.  One crucial technical difference between the two
models, which leads to two different games, is the assumption about
the initial infection: in IDS, it is assumed to originate
independently at different nodes, while in our $\GNS{1}$ model, we
assume an initial location is selected according to a given
probability distribution.
}

\junk{Mathematics models have played an important roll in mass vaccination
programs
. Two
epidemic models are commonly used when studying the spreads of
epidemics, the Susceptible-Infected-Susceptible (SIS) model and the
Susceptible-Infected-Recovery (SIR) model. The main difference between
these two models is, a recovered individual can be infected again in
the SIS model, but not in the SIR model which assumes recovered
individuals have life long immunity to the disease. And this
difference makes them suitable for different kinds of problems. For
instance, when studying childhood diseases which individuals can have
long-lasting immunity, either naturally or from vaccination, it is
more appropriate to use SIR model; when studying viruses transmitting
over the Internet, often times it is more reasonable to use SIS model,
since most of the viruses mutate, in which case even if a computer is
cured by anti-virus software and therefore not susceptible to the
original virus, it is still susceptible to a mutated virus.
}






